package org.alg.graph;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 无向图
 * @author Administrator
 *
 */
public class Graph {
	private final int V; //顶点数目
	private int E; //边的数目
	private Map<Integer,HashSet<Integer>> adj; //邻接表
	
	/**
	 * 创建一个含有V个顶点但不包含有边的图
	 * @param V
	 */
	public Graph(int V){
		this.V=V;
		this.E=0;
		adj=new HashMap<Integer,HashSet<Integer>>();
	}
	
	/**
	 * 从标准输入流in读入一幅图
	 * @param in
	 * @throws java.io.IOException
	 */
	public Graph(InputStream in) throws IOException{
		BufferedReader reader=new BufferedReader(new InputStreamReader(in));
		
		this.V=Integer.parseInt(reader.readLine());
		this.E=Integer.parseInt(reader.readLine());
		adj=new HashMap<Integer,HashSet<Integer>>();
		for(int i=0;i<E;i++){
			//添加一条边
			String line=reader.readLine();
			String[] nums=line.split(" ");
			int v=Integer.parseInt(nums[0]); //读取一个顶点
			int e=Integer.parseInt(nums[1]); //读取另一个顶点
			addEdge(v,e);
			
		}
	}
	
	/**
	 * 向图中添加一条边
	 * @param v
	 * @param w
	 */
	public void addEdge(int v,int w){
		HashSet<Integer> vSet=adj.get(v);
		if(vSet==null){
			vSet=new HashSet<Integer>();
			adj.put(v,vSet);
		}
		vSet.add(w);
		
		HashSet<Integer> wSet=adj.get(w);
		if(wSet==null){
			wSet=new HashSet<Integer>();
			adj.put(w, wSet);
		}
		wSet.add(v);
	}
	
	/**
	 * 顶点数
	 * @return
	 */
	public int V(){
		return V;
	}
	
	/**
	 * 边数
	 * @return
	 */
	public int E(){
		return E;
	}
	
	
	/**
	 * 和v相邻的所有顶点
	 * @param v
	 * @return
	 */
	public Iterable<Integer> adj(int v){
		HashSet<Integer> vSet=adj.get(v);
		return vSet;
	}
	
	/**
	 * 
	 */
	public String toString(){
		String s=V+" vertices,"+E+" edges\n";
		for(int v=0;v<V;v++){
			s+=v+":";
			for(int w:this.adj.get(v)){
				s+=w+" ";
			}
			s+="\n";
				
		}
		return s;
	}
	
	public static void main(String[] args) throws IOException{
		File f=new File("D:\\arg-data\\tinyG.txt");
		FileInputStream fis=new FileInputStream(f);
		Graph graph=new Graph(fis);
		System.out.println(graph.toString());
	}
}
